#pragma once

// 移植SGI STL二级空间配置器内存池源码
// 需要考虑多线程访问容器时的线程安全问题
//

#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <mutex>
template <typename T>
class myallocator {
public:
    using value_type = T;

    myallocator() noexcept {
        // do nothing
    }

    myallocator(const myallocator&) noexcept = default;

    template <typename _Other>
    myallocator(const myallocator<_Other>&) noexcept {
        // do nothing
    }

    // 开辟内存
    T* allocate(size_t __n) {
        __n = __n * sizeof(T);  // 将对象个数转化为内存字节数
        void* __ret = nullptr;
        if (__n > (size_t)_MAX_BYTES) {
            __ret = malloc(__n);  // 超出128字节的大块内存直接使用malloc开辟内存
        } else {
            _Obj* volatile* __my_free_list =
                _S_free_list + _S_freelist_index(__n);
            std::lock_guard<std::mutex> guard(mtx);

            _Obj* __result = *__my_free_list;
            if (__result == nullptr) {
                // 该自由链表还没有分配内存或没有空闲的内存块了
                __ret = _S_refill(_S_round_up(__n));
            } else {
                // 自由链表指向下一个空闲chunk块
                *__my_free_list = __result->_M_free_list_link;
                __ret = __result;  // 分配出去一小块chunk块
            }
        }
        return (T*)__ret;
    }

    // 释放内存
    void deallocate(void* __p, size_t __n) {
        __n = __n * sizeof(T);  // 将对象个数转化为内存字节数
        if (__n > (size_t)_MAX_BYTES) {
            free(__p);  // 超出128字节 使用free回收
        } else {
            _Obj* volatile* __my_free_list =
                _S_free_list + _S_freelist_index(__n);
            _Obj* __q = (_Obj*)__p;
            std::lock_guard<std::mutex> guard(mtx);
            __q->_M_free_list_link = *__my_free_list;
            *__my_free_list = __q;
        }
    }

    // 内存扩容&缩容
    void* reallocate(void* __p, size_t __old_sz, size_t __new_sz) {
        void* __result;
        size_t __copy_sz;

        if (__old_sz > (size_t)_MAX_BYTES && __new_sz > (size_t)_MAX_BYTES) {
            return (realloc(__p, __new_sz));
        }

        if (_S_round_up(__old_sz) == _S_round_up(__new_sz))
            return (__p);  // 不进行扩容

        __result = allocate(__new_sz);
        __copy_sz = __new_sz > __old_sz ? __old_sz : __new_sz;
        memcpy(__result, __p, __copy_sz);
        deallocate(__p, __old_sz);
        return (__result);
    }

    // 对象构造
    template <typename Ty>
    void construct(T* __p, T&& val) {        // 引用折叠
        new (__p) T(std::forward<Ty>(val));  // 完美转发
    }

    // 对象析构
    void destroy(T* __p) {
        __p->~T();
    }

private:
    // 将__bytes 上调至最邻近的8的倍数
    static size_t _S_round_up(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
    }

    // 返回 __bytes大小的chunk块位于 free-list 中的编号
    static size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);
    }

    // 将分配好的chunk块进行连接
    static void* _S_refill(size_t __n) {
        int __nobjs = 20;  // 默认chunk块的个数
        char* __chunk = _S_chunk_alloc(__n, __nobjs);  // 开辟内存
        _Obj* volatile* __my_free_list;  // 用于遍历 该字节大小对应的自由链表
        _Obj* __result;
        _Obj* __current_obj;
        _Obj* __next_obj;
        int __i;

        if (1 == __nobjs) return (__chunk);

        // 指向该字节大小的起始节点（指向该字节大小对应的自由链表）
        __my_free_list = _S_free_list + _S_freelist_index(__n);

        // 链接自由链表
        __result = (_Obj*)__chunk;
        *__my_free_list = __next_obj =
            (_Obj*)(__chunk + __n);  // +__n是因为第一个chunk块被分配出去了
        for (__i = 1;; __i++) {
            __current_obj = __next_obj;
            __next_obj = (_Obj*)((char*)__next_obj + __n);
            if (__nobjs - 1 == __i) {
                __current_obj->_M_free_list_link = nullptr;
                break;
            } else {
                __current_obj->_M_free_list_link = __next_obj;
            }
        }
        return (__result);
    }

    // 负责分配chunk块， 最核心的代码
    static char* _S_chunk_alloc(size_t __size, int& __nobjs) {
        char* __result;
        size_t __total_bytes = __size * __nobjs;  // 总共需要分配的内存大小
        size_t __bytes_left =
            _S_end_free - _S_start_free;  // 备用空间的内存大小

        if (__bytes_left >= __total_bytes) {
            // 备用空间剩余内存足够分配给所需要的内存
            __result = _S_start_free;
            _S_start_free += __total_bytes;  // 更新备用空间起始地址
            return (__result);
        } else if (__bytes_left >= __size) {
            // 备用空间不足以分配所需内存 但大于一个所需内存chunk块的大小
            __nobjs = (int)(__bytes_left /
                            __size);  // 剩余内存足够分配的chunk块的个数
            __total_bytes = __size * __nobjs;
            __result = _S_start_free;  // 分配出去的内存块
            _S_start_free += __total_bytes;
            return (__result);
        } else {
            // 备用空间过小，不足以分配一个chunk块

            // 将剩余的内存放到合适的自由链表中, 不浪费一点空间
            if (__bytes_left > 0) {
                _Obj* volatile* __my_free_list =
                    _S_free_list +
                    _S_freelist_index(
                        __bytes_left);  // 找到对应合适的自由链表头节点
                ((_Obj*)_S_start_free)->_M_free_list_link =
                    *__my_free_list;  // 剩余空间的大小应该是刚好匹配一个对应的chunk块
                // 将该剩余空间链接到自由链表中
                *__my_free_list = (_Obj*)_S_start_free;
            }

            // 开始分配新的大块空间
            size_t __bytes_to_get =
                2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
            _S_start_free = (char*)malloc(__bytes_to_get);
            if (nullptr == _S_start_free) {
                // 大块内存分配失败，尝试从更大chunk块的自由链表中取出一个空闲chunk块，用于分配
                size_t __i;
                _Obj* volatile* __my_free_list;
                _Obj* __p;
                for (__i = __size; __i <= (size_t)_MAX_BYTES;
                     __i += (size_t)_ALIGN) {
                    __my_free_list = _S_free_list + _S_freelist_index(__i);
                    __p = *__my_free_list;
                    if (nullptr != __p) {
                        // 找到可用的更大一点的chunk块
                        *__my_free_list = __p->_M_free_list_link;
                        _S_start_free = (char*)__p;
                        _S_end_free = _S_start_free + __i;
                        return (_S_chunk_alloc(
                            __size,
                            __nobjs));  // 下一次进入时再分配到对应的自由链表中
                    }
                }
                // 如果运行到这里
                // 则说明其它类型的chunk块也没有剩余的了，只能尝试继续malloc
                _S_end_free = nullptr;
                _S_start_free = (char*)malloc(
                    __bytes_to_get);  // 要么分配成功 要么抛出bad_alloc异常
            }
            _S_heap_size += __bytes_to_get;  // 一直累加已分配的内存大小
            _S_end_free = _S_start_free + __bytes_to_get;
            return (_S_chunk_alloc(
                __size,
                __nobjs));  // 下一次进入时再分配到对应的自由链表中
        }
    }

private:
    enum {
        _ALIGN = 8
    };  // 自由链表从8字节开始，以8字节为对齐方式，一直扩充到128字节
    enum { _MAX_BYTES = 128 };  // 内存池最大的chunk块的内存大小为128字节
    enum { _NFREELISTS = 16 };  // 自由链表的个数(128/8)

    // 每一个chunk块的头信息
    union _Obj {
        union _Obj* _M_free_list_link;  // next 指针，指向下一个chunk块的地址
        char _M_client_data[1];
    };

    // 内存池 自由链表的起始地址
    static _Obj* volatile _S_free_list[_NFREELISTS];

    // chunk 分配相关的三个静态成员变量
    static char* _S_start_free;
    static char* _S_end_free;
    static size_t _S_heap_size;

    // 用于实现线程互斥
    static std::mutex mtx;
};

// 静态成员变量在类外定义
template <typename T>
char* myallocator<T>::_S_start_free = nullptr;

template <typename T>
char* myallocator<T>::_S_end_free = nullptr;

template <typename T>
size_t myallocator<T>::_S_heap_size = 0;

template <typename T>
typename myallocator<T>::_Obj* volatile myallocator<
    T>::_S_free_list[_NFREELISTS] = {
    nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr,
    nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr};

template <typename T>
std::mutex myallocator<T>::mtx;
